sega_genesis_graphic_compression_formatsfandomcom-20200213-history
Run-Length Encoding
Run-Length Encoding (RLE) is one of the simplest forms of compression. Concept Consider the following data: 11 10 22 10 That could be interpreted as byte $11 repeated 16 times, then byte $22 also repeated 16 times, giving this tile data: 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 This is a tile whose top half is color #1 and the bottom half is color #2. However, when you have runs of two identical bytes, there is no size difference, and a run of one identical byte wastes a byte of space. Three or more identical bytes in a row will actually compress the data. There has got to be a better way to do it. A Better Way Consider this tile data: 00 00 00 00 00 00 00 00 00 00 00 11 11 11 22 22 22 22 22 00 34 56 78 9A BB BB BB CC CC CC CC DD Notice that some runs are only one byte long. Break the data up like this: Length 11, byte 00 Length 3, byte 11 Length 5, byte 22 Bytes 00 34 56 78 9A Length 3, byte BB Length 4, byte CC Byte DD There are 6 "singleton" bytes in this data. To distinguish between singletons and repetitions, a flag byte could be used. In this byte, a 1 means read the next byte as a literal value. A 0 means indicates a run. The above data might be read like this: 09 00 01 11 03 22 00 34 56 78 9A 01 BB 02 CC DD Each row could represent one "instruction" in this tile data. There are two instructions: Singleton or repetition. The break in between the 8th and 9th rows indicates that it is time to make a new flag byte. The first group, which contains instructions for a full flag byte, consists of three runs followed by five singletons. The corresponding flag byte could be %11111000 ($F8 in hexadecimal). The flag byte would therefore be read from right to left. The flag byte should be placed before the data in each group, meaning that F8 will come before 09 00. The second group has only three bytes. The remaining five bits of the flag byte are padded out with 0's, so the flag byte would be %00000100 ($04 in hexadecimal). The final data would look like this: F8 0B 00 03 11 05 22 00 34 56 78 9A 04 03 BB 04 CC DD Note that F8 '''and the first '''04 '''are flag bytes. That's only 18 bytes, for a savings of 14 bytes. This data is 56% as big as the original. Reading the Data The rightmost bit of the flag byte is a 0, so that indicates a run. Each run is indicated by two bytes: First is equal to repeat count minus 2, and after that is the byte that will be repeated. An example of a run: For '''09 00, the 09 '''byte means to repeat 11 times, and '''00 '''is the value to repeat. Summary Flag bytes are read from right to left. A 1 means just copy the next byte as-is, and a 0 indicates a run. In each run, the first byte is the repeat count, and the second byte is the value. For the repeat count, a value of '''01 '''could mean to repeat the byte 3 times, '''02 '''is 4 times, etc. up to '''FF, which is 257 times. A repeat count byte of '''00 '''indicates the end of the data. Assembly Code RLEGfxDec: move.b (a0)+,d1 moveq #7,d3 .1: lsr.b #1,d1 bcc.b .2 move.b (a0)+,(a1)+ bra.b .4 .2: moveq #0,d2 move.b (a0)+,d2 beq.b .5 addq.w #1,d2 move.b (a0)+,d0 .3: move.b d0,(a1)+ dbra d2,.3 .4: dbra d3,.1 move.b (a0)+,d1 moveq #7,d3 bra.b .1 .5: rts That's 40 bytes, or 1.25 tiles.